local sharedLibs = game.ReplicatedStorage.SharedLibs;
local oo = require(sharedLibs.BaseLib)

Debugger = require(sharedLibs.Debugger);

local Deque = oo.class();

function Deque:constructor()
	self.head = 0; 
	self.tail = 0;
end

--- Deque implementation by Pierre 'catwell' Chapuis
--- MIT licensed (see LICENSE.txt)
function Deque:PushRight(x)
	assert(x ~= nil)
	self.tail = self.tail + 1
	self[self.tail] = x
end

function Deque:PushLeft(x)
	assert(x ~= nil)
	self[self.head] = x
	self.head = self.head - 1
end

function Deque:PeekRight()
	return self[self.tail]
end

function Deque:PeekLeft()
	return self[self.head+1]
end

function Deque:PopRight()
	if self:IsEmpty() then return nil end
	local r = self[self.tail]
	self[self.tail] = nil
	self.tail = self.tail - 1
	return r
end

function Deque:PopLeft()
	if self:IsEmpty() then return nil end
	local r = self[self.head+1]
	self.head = self.head + 1
	local r = self[self.head]
	self[self.head] = nil
	return r
end

function Deque:RotateRight(n)
	n = n or 1
	if self:IsEmpty() then return nil end
	for i=1,n do self:PushLEft(self:PopRight()) end
end

function Deque:RotateLeft(n)
	n = n or 1
	if self:IsEmpty() then return nil end
	for i=1,n do self:PushRight(self:PopLeft()) end
end

local _remove_at_internal = function(self, idx)
	for i=idx, self.tail do self[i] = self[i+1] end
	self.tail = self.tail - 1
end

function Deque:RemoveRight(x)
	for i=self.tail,self.head+1,-1 do
		if self[i] == x then
			_remove_at_internal(self, i)
			return true
		end
	end
	return false
end

function Deque:RemoveLeft(x)
	for i=self.head+1,self.tail do
		if self[i] == x then
			_remove_at_internal(self, i)
			return true
		end
	end
	return false
end

function Deque:GetLength()
	return self.tail - self.head
end

function Deque:IsEmpty()
	return self:GetLength() == 0
end

function Deque:ToArray()
	local r = {}
	for i=self.head+1,self.tail do
		r[i-self.head] = self[i]
	end
	return r
end

function Deque:GetIterRight()
	local i = self.tail+1
	return function()
		if i > self.head+1 then
			i = i-1
			return self[i]
		end
	end
end

function Deque:GetIterLeft()
	local i = self.head
	return function()
		if i < self.tail then
			i = i+1
			return self[i]
		end
	end
end

return Deque;